class Solution {
    // 对两个字符串数字进行相加，返回字符串形式的和
    public static String twoNumSum(String s1, String s2) {
        int i = s1.length()-1, j = s2.length()-1;
        int sum = 0;
        StringBuilder builder = new StringBuilder();
        while (i >= 0 || j >= 0) {
            if (i >= 0) {
                sum += s1.charAt(i) - '0';
            }
            if (j >= 0) {
                sum += s2.charAt(j) - '0';
            }
            builder.append(sum % 10);
            sum /= 10;
            i--;
            j--;
        }
        // 可能存在进位
        if (sum != 0) {
            builder.append(sum % 10);
        }
        // 需要逆置
        return builder.reverse().toString();
    }


//    // 对两个字符串数字进行相乘，返回字符串形式的积
//    public static String multiply(String num1, String num2) {
//        // 判断字符串是否存在0
//        if ("0".equals(num1) || "0".equals(num2)) {
//            return "0";
//        }
//        String ret = "";
//        // 模拟列竖式计算
//        int count = 0; // 统计先导0
//        for (int i = num2.length()-1; i >= 0; i--) {
//            StringBuilder temp = new StringBuilder();
//            // 计算先导0
//            for (int j = 0; j < count; j++) {
//                temp.append(0);
//            }
//            count++;
//            // 计算 num2的每一个位 与 num1 的乘积
//            int product = 0; // 存储乘积
//            int a = num2.charAt(i) - '0';
//            for (int j = num1.length()-1; j >= 0; j--) {
//                int b = num1.charAt(j) - '0';
//                product = a * b + product; // 原始乘积+进位
//                temp.append(product % 10);
//                product /= 10;
//            }
//            // 进位可能不为0
//            if (product != 0) {
//                temp.append(product % 10);
//            }
//            // 将乘积进行相加（"两数"之和）
//            ret = twoNumSum(ret, temp.reverse().toString());
//        }
//        return ret;
//    }

    // 对两个字符串数字进行相乘，返回字符串形式的积
    public static String multiply(String num1, String num2) {
        // 判断字符串是否存在0
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        // 先逆序字符串
        String s1 = new StringBuilder(num1).reverse().toString();
        String s2 = new StringBuilder(num2).reverse().toString();
        int n1 = s1.length(), n2 = s2.length();
        // 申请一个数组存放乘积
        int[] temp = new int[n1+n2-1];
        // 计算 num2的每一个位 与 num1 的乘积
        for (int i = 0; i < n2; i++) {
            int a = s2.charAt(i) - '0';
            for (int j = 0; j < n1; j++) {
                int b = s1.charAt(j) - '0';
                temp[i+j] +=  a*b; // 一定要加上原来的值
            }
        }
        // 将数组的每一位转换成标准表示形式（"两数"相加的思路）
        int i = 0;
        StringBuilder builder = new StringBuilder();
        int sum = 0;
        while (i < n1+n2-1) {
            sum += temp[i];
            builder.append(sum % 10);
            sum /= 10;
            i++;
        }
        // 可能存在进位不为0的情况
        if (sum != 0) {
            builder.append(sum % 10);
        }
        // 注意要逆置
        return builder.reverse().toString();
    }

    public static void main(String[] args) {
        System.out.println(multiply("9", "99"));
    }
}